iT邦幫忙

2024 iThome 鐵人賽

DAY 18
1

引言

昨天,我們完成排序演算法的動畫架構,接下來,讓我們將各種排序方法逐步實現並植入動畫,製作逐格動畫效果!這樣的視覺化能讓我們清楚看到數據排序的過程,並進一步探討每個排序演算法的核心邏輯。

泡沫排序

https://ithelp.ithome.com.tw/upload/images/20241001/201351976TPpQpqQH9.png

線上查看動畫效果

泡沫排序(Bubble Sort)是一種簡單的排序演算法。其基本原理是通過多次遍歷陣列,每次比較相鄰元素,將較大的元素「冒泡」到陣列末端,直到完全排序。

function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 交換
            }
        }
    }
    return arr;
}

該範例便是用雙層迴圈來遍歷數列,每次將較大的數值「冒泡」到數列的後面。這樣不斷重複,直到整個數列有序。也因此時間複雜度為 O(n²),性能也較差。

解構 for 迴圈

讓我們深入了解 for 迴圈中最關鍵的三個要素:初始值條件判斷累加更新,我們先將內層的迴圈拿出來看:

for (let j = 0; j < n - 1 - i; j++) {
    if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 交換
    }
}

它可以改寫成:

let j = 0;
for (; ; ) {
    if(j < n - 1 - i) break;
    if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 交換
    }
    j++;
}

透過這種方式,我們能手動控制每次迴圈的變量變化,並清楚呈現每一輪的交換步驟。

迭代方程式

接著,我們可以不依賴傳統的 for 迴圈,而是將索引 i 和 j 存儲在類別屬性中。在這裡,我們每次將索引值賦值給 (i, j),用以區別更新後和更新前的索引值。

class SortAlgorithm{
    bubbleSortSetting(columns){
        this.i = 0;
        this.j = 0;
    }
    bubbleSort(columns){
        const len = columns.length;
        const i = this.i;
        const j = this.j;
        if (i == len - 1) return true;
        if (j == len - 1 - i) {
            this.j = 0;
            this.i++;
            return false;
        }
        const a = columns[j];
        const b = columns[j + 1];
        if (a.height > b.height) SortAlgorithm.swapColumn(a, b, 30);
        this.j++;
        return false;
    }
}
  • swapColumn:這是一個用來完成交換動畫的靜態方法,詳細請閱讀昨天的文章!

逐步更新與返回值

回顧昨天的動畫架構,我們用 return 來控制是否結束當前迭代。透過返回布林值,判斷排序是否已完成,從而停止動畫更新。

class SortAlgorithm{
    update(columns){
        if(!this.isSorting) return;

        this.times = this.timesEveryFrame;
        while(this.times--){
            const isStoping = this.sortFunction(columns);
            //......
        }
        //......
    }
}

這樣的設計讓我們能夠輕鬆控制動畫的進行與暫停,還能動態調整排序進度,確保每一步的狀態都能即時反映在動畫中。

迭代器和生成器

然而,以上方法雖然可行,可讀性卻很差呀!為了解決這個問題,我們可以使用 JavaScript 的原生功能 —— 生成器(Generator),這是一個強大的工具,能夠幫助我們實現更加簡潔和易於理解的代碼結構。

生成器函數通過 yield 關鍵字來逐步返回值,並且可以在每次迭代時保持狀態。因此,我們可以使用生成器來重構泡沫排序,讓它更具可讀性。

class SortAlgorithmIterable{
    * bubbleSortMaker(columns) {
        const len = columns.length;
        for (let i = 0; i < len - 1; i++) {
            for (let j = 0; j < len - 1 - i; j++) {
                const a = columns[j];
                const b = columns[j + 1];
                if (a.height > b.height) SortAlgorithm.swapColumn(a, b, 30);
                yield false;
            }
        }
        yield true;
    }
}

透過這個方法,我們可以完整包裝演算法,初始值的設定也可以在裡面完成。並且簡化了狀態管理。因為生成器會在每次 yield 後自動記住函數的執行狀態,我們不再需要手動管理迴圈變量的更新,如 i 和 j。

相對直觀的架構

在架構上,每次排序的時候都會透過生成器函數來製作迭代器,儲存至 sortFunction。然後,透過 next() 方法呼叫下次迭代、value 取得返回值。

class SortAlgorithmIterable{
    start(name, columns){
        this.sortFunction = this[name + "Maker"](columns);
        this.isSorting = true;
    }
    update(){
        if(!this.isSorting) return;

        this.times = this.timesEveryFrame;
        while(this.times--){
            const isStoping = this.sortFunction.next().value;
            //......
        }
        //......
    }
}

選擇排序

選擇排序是一種簡單直觀的排序演算法。它每次從未排序的部分找到最小(或最大)的元素,並將其與該部分的第一個元素交換。這個過程會重複,直到整個陣列都排好序。

function selectionSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // 交換
        }
    }
    return arr;
}

這個範例展示了選擇排序的基本操作邏輯,時間複雜度為 O(n²),對於小規模數據集,它的效率尚可,但對於大型數據集,則表現不佳。

迭代方程式

對於動態排序動畫,我們可以手動管理排序的狀態,如下:

class SortAlgorithm{
    selectionSortSetting(){
        this.i = 0;
        this.j = 1;
        this.minIndex = 0;
    }
    selectionSort(columns){
        const len = columns.length;
        const i = this.i;
        const j = this.j;
        const minIndex = this.minIndex;
        if (i == len - 1) return true;
        if (j == len) {
            this.i++;
            this.minIndex = this.i;
            this.j = this.i + 1;
            if(i == minIndex) return false;
            const a = columns[i];
            const b = columns[minIndex];
            const frame = 60;
            SortAlgorithm.swapColumn(a, b, frame);
            return false;
        }
        const min = columns[minIndex].height;
        const next = columns[j].height;
        if (next < min) this.minIndex = j;
        this.j++;
    }
}

這裡我們手動管理了 i 和 j 的狀態,並且在每次迭代時更新最小值 minIndex,最後在找到最小值後執行交換。

迭代器和生成器

當我們考慮使用生成器時,可以讓選擇排序的流程更簡潔,並將狀態保存在生成器內部:

class SortAlgorithmIterable{
    * selectionSortMaker(columns) {
        const len = columns.length;
        for (let i = 0; i < len; i++) {
            let minIndex = i;
            for (let j = i + 1; j < len; j++) {
                const min = columns[minIndex].height;
                const next = columns[j].height;
                if (next < min) minIndex = j;
                yield false;
            }
            if(minIndex == i) continue;
            const a = columns[i];
            const b = columns[minIndex];
            SortAlgorithm.swapColumn(a, b, 30);
        }
        yield true;
    }
}

這段代碼透過生成器優雅地管理選擇排序的步驟,每次 yield 都會暫停當前的操作,等待下一次的迭代。相信看到這,大家也能明白迭代生成器的強大了!

結論

使用生成器不僅讓排序的邏輯更加清晰,還提高了代碼的可讀性和維護性。對於動畫系統來說,生成器的逐步執行特性也使得我們可以精確控制每一幀的渲染,進而創造出更流暢和直觀的排序動畫。

坦白說,我原先把八種排序演算法逐一拆解,使用手動狀態管理的方式來實現動畫,後來才想到可以利用生成器來簡化這個過程。所以,作為經驗分享,接下來文章就順便一併提供大家,相信能帶來不一樣的想法!


上一篇
C2 讓排序演算法起舞吧!最小單位:華爾滋
下一篇
C4 流動的插入和希爾-迭代生成器驅動的排序動畫
系列文
讓演算法起舞:前端特效應用的探索之旅35
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言